
#include "llist.h"

/* Initialize a new singly linked list */
list_t *make_empty_list (void)
{
    list_t* new;

    new = safe_malloc(sizeof(list_t));
    new->head = NULL;
    new->foot = NULL;
    new->list_len = 0;

    return new;
}

/* Free a list and all satellite data */
void free_list (list_t *list, void (*destroy_fptr)(void *))
{
    lnode_t *cur,*next;

    cur = list->head;
    next = NULL;

    while( cur != NULL ) {
        next = cur->next;
        destroy_fptr(cur->data);
        free(cur);
        cur = next;
    }
}

/* create new list node */
lnode_t* new_node(void* data)
{
    lnode_t* new;
    new = safe_malloc( sizeof(lnode_t) );
    new->data = data;
    new->next = NULL;
    return new;
}

/* Insert a new item into the list ordered according to the cmp function
 * pointer constraints. */
list_t *insert_in_order (list_t *list, void *value, 
                         int (*cmp_fptr)(const void *, const void *))
{
    lnode_t *cur,*prev,*new;

    cur = list->head;
    prev = NULL;

    while( cur != NULL && cmp_fptr(cur->data,value) < 0 ) {
        prev = cur;
        cur = cur->next;
    }

    new = new_node(value);

    if(prev) {
        new->next = prev->next;
        prev->next = new;
    } else {
        /* head */
        new->next = list->head;
        list->head = new;
    }

    if(cur==NULL) list->foot = new;

    list->list_len++;

    return list;
}

/* Insert a new item at the end of the current list */
list_t *insert_at_foot (list_t *list, void *value)
{
    lnode_t* new = new_node(value);
    if(list->foot) {
        list->foot->next = new;
        list->foot = new;
    } else {
        list->foot = new;
        list->head = new;
    }
    list->list_len++;
    return list;
}

/* Find an item in the list, return NULL if not found */
void *find_element (list_t *list, void *value, 
                    int (*cmp_fptr)(const void *, const void *))
{
    lnode_t* cur;
    cur = list->head;
    while( cur ) {
        if( cmp_fptr(cur->data,value) == 0 ) return cur->data;
        cur = cur->next;
    }
    return NULL;
}

/* Insertion sort for link list items using a user defined cmp function */
list_t *sort_list (list_t *list, int (*cmp_fptr)(const void *, const void *))
{
    lnode_t* sorted,*slast,*next;
    lnode_t* todo;
    lnode_t* tmp;
    lnode_t* prev;

    if(list->list_len < 2) return list; /* already sorted */

    sorted = list->head; /* head of sorted list */
    slast = sorted; /* foot of sorted list */
    todo = sorted->next;
    sorted->next = NULL;

    while( todo ) {
        /* insert item into sorted list */
        tmp = sorted;
        prev = NULL;
        while( tmp != NULL && cmp_fptr(tmp->data,todo->data) < 0 ) {
            prev = tmp;
            tmp = tmp->next;
        }

        next = todo->next;

        if(prev) {
            todo->next = prev->next;
            prev->next = todo;
        } else {
            todo->next = sorted;
            sorted = todo;
        }

        if(tmp==NULL) slast = todo;

        todo = next;
    }

    /* fix up head & foot */
    list->head = sorted;
    list->foot = slast;

    return list;
}



/*
 * compare a value_t to a string
 *
 */
int token_cmp(const void *v, const void* t)
{
    const value_t* val;
    const char* token;
    val = (const value_t*)v;
    token = (const char*)t;
    return strcmp(val->word,token);
}


